package com.java.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 基数排序
 *
 * @author 19252
 * @date 2020/7/19
 */
public class RadixSort {

    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();
        int[] array = new int[]{53, 3, 542, 748, 14, 214};
        radixSort.sort(array);
        // 结果
        // System.out.println(Arrays.toString(array));

        // 效率测试
        Random random = new Random();
        // 基数排序的注意要点
        // 如果有 80000000 个 int 数据 一个int型占 4个字节
        // 所以 80000000 个int 数据 总共 需要 80000000 * 4 / 1024 / 1024 / 1024 = 0.298 GB 的内存
        // 而我们在使用 基数排序的时候 需要额外创建 10 个等大小的桶来使用
        // 所以  对 80000000 个int 数据 就需要约为 3.278 GB 的内存，极易造成占用内存过多jvm 堆内存溢出
        int[] testArray = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            testArray[i] = random.nextInt(8000000);
        }

        long millis = System.currentTimeMillis();
        radixSort.sort(testArray);
        millis = System.currentTimeMillis() - millis;
        System.out.println("数据排序所需的时间：" + millis + "毫秒");
    }

    /**
     * 基数排序
     *
     * @param array
     */
    public void sort(int[] array) {
        //第义一个二维数组，表示桶来保存数据
        // 因为数的每一位的表示范围都是 0 ~ 9 所以 只需要十个桶即可
        // 为防止极端情况下 数据溢出 将每个桶的大小定为 array的长
        int[][] bucket = new int[10][array.length];
        // 因为每个桶的存放数据量是不同，所以要为每个桶定义指针，记录每个桶中的实际存放数据的数量
        // 所以 可以这样表示：pointer[0] 记录 bucket[0]中数据的数量
        int[] pointer = new int[10];
        int restNum;
        // 设定初始的最大值
        int maxNum = array[0];
        // 找出最大数
        for (int i = 0; i < array.length; i++) {
            if (maxNum < array[i]) {
                maxNum = array[i];
            }
        }
        // 获取最大数的长度
        int length = String.valueOf(maxNum).length();
        int flag = 0;
        int n = 1;
        // 根据最大数的长度来判断需要进行几次排序
        while (flag < length) {

            for (int i = 0; i < array.length; i++) {
                // 根据循环的次数来获取相应的数的余数
                restNum = array[i] / n % 10;
                // bucket[restNum] 放入求余所得余数对应的那个桶
                // pointer[restNum] 指针数组中与余数对应的位置，第一次放入初始的值都为 0
                bucket[restNum][pointer[restNum]] = array[i];
                // 对应桶的指针加 1 为下一个数的存入 做好准备
                pointer[restNum]++;

            }

            int index = 0;
            // 按照每个桶的顺序，将数据取出放入原来的数组
            for (int i = 0; i < bucket.length; i++) {
                // 如果桶中有数据，我们才将数据取出
                if (pointer[i] > 0) {
                    // 有数据，即将对应的桶中的数据取出
                    for (int j = 0; j < pointer[i]; j++) {
                        array[index] = bucket[i][j];
                        index++;
                    }
                    // 将这个桶的指针置为 0 开启下一轮 排序
                    pointer[i] = 0;
                }
            }
            // System.out.println("第"+ flag +"次排序  " + Arrays.toString(array));
            // 可循环次数减少
            flag++;
            // n 乘 10 来对 数据进行处理，使得可以获取到相应的被除数
            n = n * 10;
        }
    }
}
